#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

int getSize(ListNode *head)
{
    int size = 0;
    while (head) {
        head = head->next;
        size++;
    }
    return size;    
}

class Solution {
public:
    ListNode *rotateRight(ListNode *head, int n)  {
        if (!head) return NULL;
        int size = getSize(head); 
        n %= size;
        if (n == 0) return head;
        ListNode *slow = head, *fast = head;
        while(n> 0 && fast){ n--; fast = fast->next;}
        ////cout << n << endl;
        while (fast->next) {
           slow = slow->next;
           fast = fast->next;
        }
        ListNode *rtn = slow->next;
        slow->next = NULL;
        while (slow->next) slow = slow->next;
        fast->next = head;
        return rtn;
    }
};

ListNode *newList(int data[], int index, int size)
{
    ListNode *node = NULL;
    if (index == size)
        return node;

    node = new ListNode(data[index]);
    node->next = newList(data, index+1, size);

    return node;
}

//test on 1337 online judge and pass all the test
int main(int argc, char **argv)
{

    Solution mySolution;
    cout << "-----------------Test 1--------------------" << endl;
    int data[] = {1,4,5,6,7};
    ListNode *list1, *list2;
    list1 = newList(data, 0, sizeof(data)/sizeof(int));
    ListNode *list = mySolution.rotateRight(list1, 2);
    while(list) {
        cout << list->val << " ";
        list= list->next;
    }
    cout << endl;

}
